翻訳と辞書 Words near each other ・ Shanklin Glacier ・ Shanklin Pier Ltd v Detel Products Ltd ・ Shanklin railway station ・ Shanklin Village ・ Shanklish ・ Shankol ・ Shankou ・ Shanks ・ Shanks & Bigfoot ・ Shanks (film) ・ Shanks Group ・ Shanks House ・ Shanks Islands ・ Shanks Restaurant ・ Shanks transformation ・ Shanks' square forms factorization ・ Shanks, West Virginia ・ Shanksville Volunteer Fire Department ・ Shanksville, Pennsylvania ・ Shanksville-Stonycreek High School ・ Shanksville-Stonycreek School District ・ Shankudeb Panda ・ Shankumugham Beach ・ Shankurutty ・ Shanley ・ Shanley Caswell ・ Shanley High School ・ Shanley v. Northeast Independent School District ・ Shanley's Restaurants ・ Shanlian Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Shanks' square forms factorization ： ウィキペディア英語版 Shanks' square forms factorization Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method. The success of Fermat's method depends on finding integers $x$ and $y$ such that $x^2-y^2=N$, where $N$ is the integer to be factored. An improvement (noticed by Kraitchik) is to look for integers $x$ and $y$ such that $x^2\backslash equiv\; y^2\backslash pmod$. Finding a suitable pair $(x,\; y)$ does not guarantee a factorization of $N$, but it implies that $N$ is a factor of $x^2-y^2=(x-y)(x+y)$, and there is a good chance that the prime divisors of $N$ are distributed between these two factors, so that calculation of the greatest common divisor of $N$ and $x-y$ will give a non-trivial factor of $N$. A practical algorithm for finding pairs $(x,y)$ which satisfy $x^2\backslash equiv\; y^2\backslash pmod$ was developed by Shanks, who named it Square Forms Factorization or SQUFOF. The algorithm can be expressed in terms of continued fractions, or in terms of quadratic forms. Although there are now much more efficient factorization methods available, SQUFOF has the advantage that it is small enough to be implemented on a programmable calculator. ==Algorithm== Input: $N$, the integer to be factored, which must be neither a prime number nor a perfect square, and a small multiplier $k$. Output: a non-trivial factor of $N$. The algorithm: Initialize $P\_0=\backslash lfloor\backslash sqrt\backslash rfloor,Q\_0=1,Q\_1=kN-P\_0^2.$ Repeat $b\_i=\backslash left\backslash lfloor\backslash frac\}\backslash right\backslash rfloor,P\_i=b\_iQ\_i-P\_,Q\_=Q\_+b\_i(P\_-P\_i)$ until $Q\_i$ is a perfect square at some even $i$. Initialize $b\_0=\backslash left\backslash lfloor\backslash frac\}+P\_,Q\_0=\backslash sqrt,Q\_1=\backslash frac$ Repeat $b\_i=\backslash left\backslash lfloor\backslash frac\}\backslash right\backslash rfloor,P\_i=b\_iQ\_i-P\_,Q\_=Q\_+b\_i(P\_-P\_i)$ until $P\_i=P\_.$ Then if $f=\backslash gcd(N,P\_i)$ is not equal to $1$ and not equal to $N$, then $f$ is a non-trivial factor of $N$. Otherwise try another value of $k$. Shanks's method has time complexity $O(\backslash sqrt())$. Stephen S. McMasters (see link in External Link section) wrote a more detailed discussion of the mathematics of Shanks's method, together with a proof of its correctness. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shanks' square forms factorization」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.